{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Delete Leaves With a Given Value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeLeafNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除给定值的叶子节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵以&nbsp;<code>root</code>&nbsp;为根的二叉树和一个整数&nbsp;<code>target</code>&nbsp;，请你删除所有值为&nbsp;<code>target</code> 的&nbsp;<strong>叶子节点</strong> 。</p>\n",
    "\n",
    "<p>注意，一旦删除值为&nbsp;<code>target</code>&nbsp;的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是&nbsp;<code>target</code> ，那么这个节点也应该被删除。</p>\n",
    "\n",
    "<p>也就是说，你需要重复此过程直到不能继续删除。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/16/sample_1_1684.png\" style=\"height: 120px; width: 550px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [1,2,3,2,null,2,4], target = 2\n",
    "<strong>输出：</strong>[1,null,3,null,4]\n",
    "<strong>解释：\n",
    "</strong>上面左边的图中，绿色节点为叶子节点，且它们的值与 target 相同（同为 2 ），它们会被删除，得到中间的图。\n",
    "有一个新的节点变成了叶子节点且它的值与 target 相同，所以将再次进行删除，从而得到最右边的图。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/16/sample_2_1684.png\" style=\"height: 120px; width: 300px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [1,3,3,3,2], target = 3\n",
    "<strong>输出：</strong>[1,3,null,null,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/16/sample_3_1684.png\" style=\"width: 450px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [1,2,null,2,null,2], target = 2\n",
    "<strong>输出：</strong>[1]\n",
    "<strong>解释：</strong>每一步都删除一个绿色的叶子节点（值为 2）。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [1,1,1], target = 1\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [1,2,3], target = 1\n",
    "<strong>输出：</strong>[1,2,3]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= target&nbsp;&lt;= 1000</code></li>\n",
    "\t<li>每一棵树最多有 <code>3000</code> 个节点。</li>\n",
    "\t<li>每一个节点值的范围是&nbsp;<code>[1, 1000]</code>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [delete-leaves-with-a-given-value](https://leetcode.cn/problems/delete-leaves-with-a-given-value/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [delete-leaves-with-a-given-value](https://leetcode.cn/problems/delete-leaves-with-a-given-value/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,2,null,2,4]\\n2', '[1,3,3,3,2]\\n3', '[1,2,null,2,null,2]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, node: TreeNode, target: int) -> TreeNode:\n",
    "        if node is None:\n",
    "            return None\n",
    "        \n",
    "        node.left = self.removeLeafNodes(node.left, target)\n",
    "        node.right = self.removeLeafNodes(node.right, target)\n",
    "        \n",
    "        return (\n",
    "            None\n",
    "            if node.left is None and node.right is None and node.val == target\n",
    "            else node\n",
    "        )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        def dfs(node, parent, left):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left, node, 1)\n",
    "            dfs(node.right, node, 0)\n",
    "            if (not node.left) and (not node.right) and node.val ==target:\n",
    "                if left==1:\n",
    "                    parent.left=None\n",
    "                else:\n",
    "                    parent.right = None\n",
    "        dummy = TreeNode(-1, root, None)\n",
    "        dfs(root, dummy, 1)\n",
    "        return dummy.left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left,target)\n",
    "        root.right= self.removeLeafNodes(root.right,target)\n",
    "        if not root.left and not root.right and root.val ==target:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if(root==None):\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left,target)\n",
    "        root.right = self.removeLeafNodes(root.right,target)\n",
    "        if(root.left==None and root.right==None and root.val == target):\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return \n",
    "        left = self.removeLeafNodes(root.left,target)\n",
    "        right = self.removeLeafNodes(root.right,target)\n",
    "        root.left = left \n",
    "        root.right = right\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left  = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "\n",
    "        if root.val == target and root.left is None and root.right is None:\n",
    "            return None\n",
    "        \n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left,target)\n",
    "        root.right =  self.removeLeafNodes(root.right,target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root :\n",
    "            return None\n",
    "        \n",
    "        root.left=self.removeLeafNodes(root.left,target)\n",
    "        root.right=self.removeLeafNodes(root.right,target)\n",
    "        if root.val==target and not root.left and not root.right:\n",
    "            return None \n",
    "        return root "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        left = self.removeLeafNodes(root.left, target)\n",
    "        root.left = left\n",
    "        right = self.removeLeafNodes(root.right, target)\n",
    "        root.right = right\n",
    "        if not root.left and not root.right:\n",
    "            if root.val == target:\n",
    "                return None\n",
    "        return root\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return \n",
    "        root.left = self.removeLeafNodes(root.left,target)\n",
    "        root.right = self.removeLeafNodes(root.right,target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        def dfs(node, parent, left = True):\n",
    "            l = node.left\n",
    "            r = node.right\n",
    "            if l:\n",
    "                dfs(l, node, True)\n",
    "            if r:\n",
    "                dfs(r, node, False)\n",
    "\n",
    "            if not (node.left or node.right):\n",
    "                if node.val == target:\n",
    "                    if left:\n",
    "                        parent.left = None\n",
    "                    else:\n",
    "                        parent.right = None\n",
    "\n",
    "        dummy = TreeNode(0, root)\n",
    "        dfs(root, dummy)\n",
    "        return dummy.left\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        \n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if not left and not right and node.val == target:\n",
    "                return\n",
    "            node.left = left\n",
    "            node.right = right\n",
    "            return node\n",
    "        \n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode:\n",
    "        if root:\n",
    "            root.left = self.removeLeafNodes(root.left, target)\n",
    "            root.right = self.removeLeafNodes(root.right, target)\n",
    "            return (root.left or root.right or root.val != target) and root or None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left,target)\n",
    "        root.right = self.removeLeafNodes(root.right,target)\n",
    "        if root.val == target and not root.left and not root.right:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        def recur(node):\n",
    "            if node.left:\n",
    "                if recur(node.left):\n",
    "                    node.left = None\n",
    "            if node.right:\n",
    "                if recur(node.right):\n",
    "                    node.right = None\n",
    "            if not node.left and not node.right:\n",
    "                if node.val == target:\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        if recur(root):\n",
    "            return None\n",
    "        return root\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "         # 递归结束条件：如果当前节点为空，则返回 None\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        # 递归处理左子树和右子树\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "\n",
    "        # 如果当前节点为叶子节点且值等于 target，将其删除，返回 None\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "\n",
    "        # 返回处理后的当前节点\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if root.val == target and root.left is None and root.right is None:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        def dfs(root, parent):\n",
    "            if not root:\n",
    "                return None\n",
    "            root.left = dfs(root.left, root)\n",
    "            root.right = dfs(root.right, root)\n",
    "            if root.val == target and root.left is None and root.right is None:\n",
    "                return None\n",
    "            return root\n",
    "        return dfs(root, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        res = self.dfs(root, target)\n",
    "        if res:\n",
    "            return None\n",
    "        return root\n",
    "\n",
    "    def dfs(self, node, target):\n",
    "        if not node:\n",
    "            return True\n",
    "        resL = self.dfs(node.left, target)\n",
    "        resR = self.dfs(node.right, target)\n",
    "        if resL:\n",
    "            node.left = None\n",
    "        if resR:\n",
    "            node.right = None\n",
    "        if resL and resR and node.val == target:\n",
    "            return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left,target)\n",
    "        root.right = self.removeLeafNodes(root.right,target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return \n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return \n",
    "    \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return\n",
    "        root.left = self.removeLeafNodes(root.left,target)\n",
    "        root.right =self.removeLeafNodes(root.right,target)\n",
    "        if not root.right and not root.left and root.val == target:\n",
    "            return \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if root == None:\n",
    "            return root\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right= self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left,target)\n",
    "        root.right = self.removeLeafNodes(root.right,target)\n",
    "        if not root.left and not root.right and root.val==target:\n",
    "            return None\n",
    "        return root\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        l = self.removeLeafNodes(root.left,target)\n",
    "        r = self.removeLeafNodes(root.right,target)\n",
    "        if not l and not r and root.val == target:\n",
    "            return None\n",
    "        root.left = l \n",
    "        root.right = r\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root :\n",
    "            return None \n",
    "        \n",
    "        root.left=self.removeLeafNodes(root.left,target)\n",
    "        root.right=self.removeLeafNodes(root.right,target)\n",
    "\n",
    "        if(root.val==target and root.left is None and root.right is None):\n",
    "            return None\n",
    "        \n",
    "        return root \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        p_root = TreeNode(0)\n",
    "        p_root.left = root\n",
    "        self.dfs(p_root, target)\n",
    "    \n",
    "        return p_root.left\n",
    "\n",
    "    def dfs(self, now, target):\n",
    "        if now.left is not None and self.dfs(now.left, target):\n",
    "            now.left = None\n",
    "\n",
    "        if now.right is not None and self.dfs(now.right, target):\n",
    "            now.right = None\n",
    "\n",
    "        return now.left is None and now.right is None and now.val == target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left  = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if root.val == target and not root.left and not root.right:\n",
    "            return None\n",
    "        return root\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        def dfs(root, target):\n",
    "            if root == None:\n",
    "                return\n",
    "            root.left = dfs(root.left, target)\n",
    "            root.right = dfs(root.right, target)\n",
    "            if root.left == None and root.right == None and root.val == target:\n",
    "                root = None\n",
    "            return root\n",
    "        return dfs(root, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        \n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            if not root.left and not root.right and root.val == target:\n",
    "                return \n",
    "            return root\n",
    "        \n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root \n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        def dfs(node, parent, left = True):\n",
    "            if node.left:\n",
    "                dfs(node.left, node, True)\n",
    "            if node.right:\n",
    "                dfs(node.right, node, False)\n",
    "\n",
    "            if not (node.left or node.right) and node.val == target:\n",
    "                if left:\n",
    "                    parent.left = None\n",
    "                else:\n",
    "                    parent.right = None\n",
    "\n",
    "        dummy = TreeNode(0, root)\n",
    "        dfs(root, dummy)\n",
    "        return dummy.left\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        def dfs(root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "            if root:\n",
    "                root.left = dfs(root.left)\n",
    "                root.right = dfs(root.right)\n",
    "                if not root.left and not root.right and root.val == target:\n",
    "                    return None\n",
    "                return root\n",
    "            else:\n",
    "                return None\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        def prune(r):\n",
    "            if not r:return r\n",
    "            r.left = prune(r.left)\n",
    "            r.right = prune(r.right)\n",
    "            if r and r.val==target and not r.left and not r.right:return None\n",
    "            return r\n",
    "\n",
    "        return prune(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        \n",
    "        if root.left is None and root.right is None and root.val == target:\n",
    "            return None\n",
    "        \n",
    "        return root "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        origin = TreeNode(target, root, None)\n",
    "        def dfs(root, father, target, dir):\n",
    "            if not root: return \n",
    "            dfs(root.left, root, target, 0)\n",
    "            dfs(root.right, root, target, 1)\n",
    "            if root.val == target and not root.left and not root.right:\n",
    "                if dir == 0:\n",
    "                    father.left = None \n",
    "                else:\n",
    "                    father.right = None \n",
    "        dfs(root, origin, target, 0)\n",
    "        if not origin: return None\n",
    "        return origin.left "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if root == None: return None\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target: return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        root.left=self.removeLeafNodes(root.left,target)\n",
    "        root.right=self.removeLeafNodes(root.right,target)\n",
    "\n",
    "        if root.val==target and not root.left and not root.right:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # Postorder. Time O(n) Space O(n)\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        # return a processed subtree\n",
    "        def dfs(root):\n",
    "            if not root: return None\n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            if not root.left and not root.right and root.val == target:\n",
    "                return None\n",
    "            return root\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left=self.removeLeafNodes(root.left,target)\n",
    "        root.right=self.removeLeafNodes(root.right,target)\n",
    "        if not root.left and not root.right and root.val==target:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        def dfs(root):\n",
    "            if not root: return None\n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            if not root.left and not root.right and root.val == target:\n",
    "                return None\n",
    "            return root\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "\n",
    "        if root.left is None and root.right is None and root.val == target:\n",
    "            return None\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left=self.removeLeafNodes(root.left,target)\n",
    "        root.right=self.removeLeafNodes(root.right,target)\n",
    "        if not root.left and not root.right and root.val==target:\n",
    "                root=None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        root.left = self.removeLeafNodes(root.left,target)\n",
    "        root.right = self.removeLeafNodes(root.right,target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "            \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.left:\n",
    "            root.left=self.removeLeafNodes(root.left,target)\n",
    "        if root.right:\n",
    "            root.right=self.removeLeafNodes(root.right,target)\n",
    "        if not root.left and not root.right and root.val==target:\n",
    "                root=None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        def dfs(root):\n",
    "            nonlocal target\n",
    "\n",
    "            if root.left:\n",
    "                lflag = dfs(root.left)\n",
    "                if lflag:\n",
    "                    root.left = None\n",
    "            if root.right:\n",
    "                rlfag = dfs(root.right)\n",
    "                if rlfag:\n",
    "                    root.right = None\n",
    "            if not root.left and not root.right and root.val == target:\n",
    "                return True\n",
    "        tmp = dfs(root)\n",
    "        if tmp:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        def depth(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return max(depth(node.left), depth(node.right)) + 1\n",
    "        \n",
    "        def deleteLeaf(node):\n",
    "            if not node:\n",
    "                return \n",
    "            if node.left and not node.left.left and not node.left.right:\n",
    "                if node.left.val == target:\n",
    "                    node.left = None\n",
    "            if node.right and not node.right.left and not node.right.right:\n",
    "                if node.right.val == target:\n",
    "                    node.right = None\n",
    "            deleteLeaf(node.left)\n",
    "            deleteLeaf(node.right)\n",
    "\n",
    "        d = depth(root)\n",
    "        for i in range(d):\n",
    "            deleteLeaf(root)\n",
    "        if root and not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\r\n",
    "        nummpy = TreeNode(-1, root)\r\n",
    "        def dfs(cur, fa, isleft):\r\n",
    "            nonlocal target\r\n",
    "            if cur.left:\r\n",
    "                dfs(cur.left, cur, True)\r\n",
    "            if cur.right:\r\n",
    "                dfs(cur.right, cur, False)\r\n",
    "            if cur.val == target and not cur.left and not cur.right:\r\n",
    "                if isleft:\r\n",
    "                    fa.left = None\r\n",
    "                else:\r\n",
    "                    fa.right = None\r\n",
    "                return \r\n",
    "        dfs(root, nummpy, True)\r\n",
    "        return nummpy.left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if root.val == target and not root.left and not root.right:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return \n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.right and not root.left and root.val == target:\n",
    "            return None \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root: return None\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "        if not root.left and not root.right and root.val == target:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        while root and self.isLeafHasTarget(root,target):\n",
    "            root = self.removeNode(root,target)\n",
    "        return root\n",
    "        \n",
    "    def removeNode(self, root: Optional[TreeNode], target: int):\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.val == target and not root.left and not root.right:\n",
    "            return None\n",
    "        root.left =  self.removeLeafNodes(root.left,target)\n",
    "        root.right =  self.removeLeafNodes(root.right,target)\n",
    "        return root\n",
    "    def isLeafHasTarget(self, p, target):\n",
    "        if not p:\n",
    "            return False\n",
    "        has_taget = False\n",
    "        if   p.val == target and not p.left and not p.right:\n",
    "            return True\n",
    "        if not has_taget:\n",
    "            has_taget = self.isLeafHasTarget(p.left,target)\n",
    "        if not has_taget:\n",
    "            has_taget = self.isLeafHasTarget(p.right,target)\n",
    "        return has_taget"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "\n",
    "        if root.left is None and root.right is None and root.val == target:\n",
    "            return None\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def removeLeafNodes(self, root, target) -> Optional[TreeNode]:\n",
    "        if not root: return None\n",
    "\n",
    "        root.left = self.removeLeafNodes(root.left, target)\n",
    "        root.right = self.removeLeafNodes(root.right, target)\n",
    "\n",
    "        if root.val == target and not root.left and not root.right:\n",
    "            return None\n",
    "        \n",
    "        return root\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
